package com.suanfa.jiaoheng;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 图的实际应用，这个目标应该是判断图中是否 有目标节点,或者说图遍历的一种方式具体路径后续再研究吧
 * 解决最短领问题的算法——广度优先算法
 *    使用队列记录要检查的资源
 *    需要记录下已经处理过的结点，避免死循环
 *
 */
public class 第6课广度优先 {

    public static void main(String[] args) {
        Node startNode = 创造线路();
        广度优先算法(startNode,"稻香湖路");

    }

    // 定义图中的结点
    static class Node{
        String name;
        List<Node> nodeList = new ArrayList<>();
    }

    /**
     *
     * 呼家楼，白石桥南，国家图书馆，稻香湖路
     * 呼家楼，海淀黄庄，西苑，稻香湖路
     * 呼家楼，二里沟，稻香湖路
     */
    static Node 创造线路(){
        Node startNode = new Node();
        startNode.name = "呼家楼";

        Node 白石桥南 = new Node();
        白石桥南.name = "白石桥南";

        Node 国家图书馆 = new Node();
        国家图书馆.name = "国家图书馆";

        Node 稻香湖路 = new Node();
        稻香湖路.name = "稻香湖路";

        Node 二里沟 = new Node();
        二里沟.name = "二里沟";

        Node 海淀黄庄 = new Node();
        海淀黄庄.name = "海淀黄庄";

        Node 西苑 = new Node();
        西苑.name = "西苑";

        // 开始设置其list
        startNode.nodeList.add(白石桥南);
        startNode.nodeList.add(海淀黄庄);
        startNode.nodeList.add(二里沟);

        白石桥南.nodeList.add(国家图书馆);
        国家图书馆.nodeList.add(稻香湖路);

        海淀黄庄.nodeList.add(西苑);
        西苑.nodeList.add(稻香湖路);

        二里沟.nodeList.add(稻香湖路);

        return startNode;
    }

    static void 广度优先算法(Node startNode,String targetNodeName){
        Set<Node> haveChecked = new HashSet<>();
        Queue<Node> checkQueue = new LinkedBlockingQueue<>();

        checkQueue.add(startNode);
        haveChecked.add(startNode);

        Node currentNode = null;
        while(!checkQueue.isEmpty()){
            currentNode = checkQueue.poll();
            System.out.println("访问过的路径:"+currentNode.name);
            if(currentNode.name.equals(targetNodeName)){
                System.out.println("已找到目标节点:"+targetNodeName);
                return;
            }
            currentNode.nodeList.stream().forEach(node -> {
                // 如果已经添加过就不再二次添加
                if(haveChecked.contains(node)){
                    return;
                }
                checkQueue.add(node);
                haveChecked.add(node);
            });
        }
        System.out.println("未找到目标节点");
    }
}
